const nodes = [1, 2, 3, null, null, 6, null, null, 9, null, 11];

let binaryTree = createBinaryTree(nodes)
console.log('binaryTree: ', binaryTree);

// -------------------------------------构造树-----------------------------------------------
function createBinaryTree(treeArr) {
  if (!treeArr.length) return null
  let node = null
  data = treeArr.shift()
  // 注意这里按照数组创建树，用是否有data判断当前节点是否存在，如果数组没有null，则会创建出一个只有左节点的树
  if (data) {
    node = createNode(data)
    node.leftChild = createBinaryTree(treeArr)
    node.rightChild = createBinaryTree(treeArr)
  }
  return node

}

// 创建包含左右子节点的树节点
function createNode(value) {
  if (!value) return null
  let node = {}
  node.value = value
  node.leftChild = null
  node.rightChild = null
  return node
}

// 构造的树
const tree = {
  "value": 1,
  "leftChild": {
    "value": 2,
    "leftChild": {
      "value": 3,
      "leftChild": null,
      "rightChild": null
    },
    "rightChild": {
      "value": 6,
      "leftChild": null,
      "rightChild": null
    }
  },
  "rightChild": {
    "value": 9,
    "leftChild": null,
    "rightChild": {
      "value": 11,
      "leftChild": null,
      "rightChild": null
    }
  }
}

// ------------------------------------前序遍历----------------------------------------------
// 输出顺序：根节点、左子树、右子树
// 规则：从上到下，只有左子节点，就逐层向下遍历左子节点，直到左子节点遍历完，就遍历同层级右子节点，然后逐层向上返回，遍历右子节点，如果此时右子节点又有左子节点，则继续向下遍历至左子节点遍历完
function preOrder(node) {
  if (!node) return
  console.log(node.value)
  preOrder(node.leftChild)
  preOrder(node.rightChild)
}
console.log(`前序遍历`)
preOrder(binaryTree)

// ------------------------------------中序遍历----------------------------------------------
// 输出顺序：左子树、根节点、右子树
function inOrder(node) {
  // 这里会一直从根节点向下遍历左节点，当最后一个左节点为null时，就结束向下的遍历，回到它上层的inOrder方法里，输出当前在inOrder方法里的节点（即倒数第二个左节点）的value；
  // 然后再把对应同一父节点的右节点放进inOder方法进行同样的遍历
  if (!node) return
  inOrder(node.leftChild)
  console.log(node.value)
  inOrder(node.rightChild)
}
console.log(`中序遍历`)
inOrder(binaryTree)

// ------------------------------------后序遍历----------------------------------------------
// 输出顺序：左子树、右子树、根节点
function postOrder(node) {
  if (!node) return
  postOrder(node.leftChild)
  postOrder(node.rightChild)
  console.log(node.value)
}
console.log(`后序遍历`)
postOrder(binaryTree)
